\section{Preliminaries}

This section will review some basic definitions of two-dimensional languages. The notions are mainly from ~\cite{giammarresi1997twodimensional} and~\cite{cherubini2009picture}.

\begin{definition}
	Let $\Sigma$ be a finite non-empty set. A two-dimensional array over $\Sigma$ is called a picture over $\Sigma$, where any position in the array must contain exactly one symbol of $\Sigma$. The set of pictures over $\Sigma$ is denoted as $\Sigma^{*, *}$. 
\end{definition}

Any subset $L \subseteq \Sigma^{*, *}$ is called a two-dimensional language. 

Let $p$ be a picture. The number of rows and columns are denoted as $|p|_r$ and $|p|_c$ respectively. The size of a picture p is denoted as $|p| = (|p|_r, |p|_c)$ and is the pair of width and height of the picture. The empty picture is denoted as $\lambda$ and is the only picture of size $(0, 0)$. 

A single pixel of a picture $p$ is denoted as $p(i, j)$ for $1 \leq i \leq |p|_r$ and $1 \leq j \leq |p|_c$. Therefore, we are able to represent a picture by the content of its positions: 

\begin{center}
	$p =$ \begin{tabular}{|ccc|}
		\hline
		$p(1, 1)$       & \dots     & $p(1, |p|_c)$ \\
		$\vdots$        & $\ddots$  & $\vdots$  \\
		$p(|p|_r, 1)$   & \dots     & $p(|p|_r, |p|_c)$ \\
		\hline
	\end{tabular}
\end{center}

We can define the concatenation from the one-dimensional case, but we have to split into column and row concatenation operations: 

\begin{definition}
	Let $\Sigma$ be an finite non-empty alphabet and $p, q \in \Sigma^{*, *}$ be two pictures with $|p|_c = |q|_c$. The column concatenation is defined as \[p \hcat q = 
	\begin{tabular}{|cccccc|}
		\hline
		$p(1, 1)$       & \dots     & $p(1, |p|_c)$     & $q(1, 1)$     & \dots    & $q(1, |q|_c$ \\
		$\vdots$        & $\ddots$  & $\vdots$          & $\vdots$      & $\ddots$ &  $\vdots$ \\
		$p(|p|_r, 1)$   & \dots     & $p(|p|_r, |p|_c)$ & $q(|p|_r, 1)$ & \dots   & $q(|q|_r, |q|_c)$ \\
		\hline
	\end{tabular}\] 
\end{definition}

Note that the column concatenation is only defined, if the number of columns of $p$ is equal to the number of columns of $q$. The row-concatenation can be defined similarly and is denoted as $p \vcat q$. 

\begin{definition}
	Let $L_1, L_2 \subseteq \Sigma^{*, *}$ be two two-dimensional languages. The column concatenation of languages is defined as: 
	
	\[L_1 \hcat L_2 = \{p \hcat q \mid p \in L_1 \text{ and } q \in L_2\}. \]
\end{definition}

The row concatenation of languages is similarly defined. 

The Kleene star, known from the one-dimensional case also needs to be separated into two different operators:

\begin{definition}
	Let $L$ be a two-dimensional language. The column closure is defined as
	
	\[L^{*\hcat} = \underset{i \geq 0}{\bigcup} L^{i \hcat} \text{ with } L^{0 \hcat} = \{\lambda\}, L^{n \hcat} = L \hcat L^{(n-1) \hcat}\]
\end{definition}

Similarly, the row closure of two-dimensional languages is defined. 

When speaking about morphisms for pictures, we have to handle the problem of 'shearing' \cite{siromoney1986advances}. 'Shearing' means, that if a sub-picture is replaced by a picture of different size, the image is not valid any more. Therefore, the definition of two-dimensional morphisms require the morphisms to permit 'shearing'. The following definitions are from \cite{siromoney1973picture}. 

\begin{definition}
	Let $\Sigma_1$ and $\Sigma_2$ be two alphabets. A mapping $H: \Sigma_1^{*, *} \rightarrow \Sigma_2^{*, *}$ is a \emph{two-dimensional morphism} if $H(u \vcat v) = H(u) \vcat H(v)$ and $H(u \hcat v) = H(u) \hcat H(v)$ for all $u, v \in \Sigma_1^{*, *}$. 
\end{definition}

Let $H: \Sigma_1^{*, *} \rightarrow \Sigma_2^{*, *}$ be a two-dimensional morphism. $H$ is called $\epsilon$-free, if $H(a) \neq \epsilon$ for all $a \in \Sigma_1$. Furthermore, let $L \subset \Sigma_1^{*, *}$ be a two-dimensional language. The morphism can be applied to the whole language which is written as $H(L) = \{H(x) \mid x \in L\}$. 

In the following, we will also use \emph{column morphisms}, which are restricted such that $|h(a)|_c = 1$ for all $a \in \Sigma_1$. The use of column morphisms will be indicated by a lower-case $h$. 

This definition permits the change of the number of columns by a morphism. That is shown by the following proposition. 

\begin{proposition}
	Let $\Sigma_1, \Sigma_2$ be two alphabets, $h: \Sigma_1^{*, *} \rightarrow \Sigma_2^{*, *}$ be a column morphism and $p \in \Sigma_1^{*, *}$. Then $|p|_c = |h(p)|_c$. 
\end{proposition}

\begin{proof}
	We proof this by induction. For $a \in \Sigma_1$ $|a|_c = 1 = |h(a)|_c$ holds per definition of $h$. Let $p \in \Sigma_1^{*, *}$ be a picture with $|p| = (m, n)$ and $c \in \Sigma_1^{*, *}$ be a picture with $|c| = (m, 1)$. Then $|p \hcat c|_c = |p|_c + |c|_c = |h(p)|_c + |h(c)|_c = |h(p) \hcat h(c)| = |h(p \hcat c)|$ holds. 
\end{proof}

The definition of two-dimension morphisms induce, that the size of each image of a single character is always the same. This is proved in the next proposition. 

\begin{proposition}
\label{proposition:morphism_size_of_single_letters}
	Let $\Sigma_1, \Sigma_2$ be two alphabets and $H: \Sigma_1^{*, *} \rightarrow \Sigma_2^{*, *}$ be a two-dimensional morphism, then the following holds:

	For all $a, b \in \Sigma_1$: $|H(a)| = |H(b)|$. 
\end{proposition}

\begin{proof}
	Let $p = a \hcat b$ be a picture. Per definition of two-dimensional morphisms holds that $|H(a \hcat b)| = |H(a) \hcat H(b)|$. Because column concatenation is only defined, if $|H(a)|_r = |H(b)|_r$, the number of rows of $H(a)$ and $H(b)$ must be equal. This can similarly be shown for the number of columns. 
\end{proof}

\begin{corollary}
	Let $\Sigma_1, \Sigma_2$ be two alphabets, $h: \Sigma_1^{*, *} \rightarrow \Sigma_2^{*, *}$ be a colum morphism, $p \in \Sigma_1^{*, *}$ be a picture and $s = |h(a)|_r$ for some $a \in \Sigma_1$. Then $|h(p)|_r = k \cdot s$ for some $k \in \mathbb{N}$. 
\end{corollary}

\begin{definition}
	Let $H: \Sigma_1^{*, *} \rightarrow \Sigma_2^{*, *}$ be a two-dimensional morphism. We call $H^{-1}: \Sigma_2^{*, *} \rightarrow 2^{\Sigma_1^{*, *}}$ an inverse morphism, where $x \mapsto \{y \in \Sigma_1 \mid H(y) = x\}$ for all $x \in \Sigma_2^{*, *}$. 
\end{definition}

Originally, \cite{ginsburg1967abstract} stated, that an \emph{abstract family of languages} must contain at least one language which is not empty and is closed under the six operations of union, concatenation, Kleene closure, $\epsilon$-free morphism, inverse morphism and intersection with regular sets. Because the matrix languages are not closed under these operations in general, the Sironmoney's introduced the following restricted version in \cite{giftsironmoneyranisironmoney1972abstract}:

\begin{definition}
	An \emph{abstract family of matrices} is a class of two-dimensional formal languages which is closed under union, column concatenation, column closure, $\epsilon$-free column morphism, inverse column morphism and intersection with a regular matrix language. 
\end{definition}

Before we consider two-dimensional languages generated by matrix grammars, we recall the definition of growing context-sensitive languages. 